package com.echo.code.arithmetic.chapter07;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * Created by baiyap on 2018/8/15.
 */
public class Dijkstra {

  public static void main(String[] args) {
    // create and initialize graph
    HashMap<String, HashMap<String, Float>> graph = new HashMap<>();
    graph.put("start", new HashMap<String, Float>() {{
      put("a", 6f);
      put("b", 2f);
    }});
    graph.put("a", new HashMap<String, Float>() {{
      put("fin", 1f);
    }});
    graph.put("b", new HashMap<String, Float>() {{
      put("a", 3f);
      put("fin", 5f);
    }});

    HashMap<String, Float> costs = new HashMap<String, Float>() {{
      put("a", 6f);
      put("b", 2f);
      put("fin", Float.POSITIVE_INFINITY);
    }};

    HashMap<String, String> parents = new HashMap<String, String>() {{
      put("a", "start");
      put("b", "start");
      put("fin", null);
    }};

    List<String> processed = new LinkedList<>();
    // dijkstra's algorithm
    final Optional<String> node = Optional.getInstance(find_lowest_cost_node(costs, processed));
    while (Objects.nonNull(node.getValue()) && !Objects.equals(node.getValue(), "fin")) {
      final float cost = costs.get(node.getValue());
      HashMap<String, Float> neighbors = graph.get(node.getValue());
      // 遍历当前节点的所有邻居
      neighbors.forEach((key, value) -> {
        float new_cost = value + cost;
        if (new_cost < costs.get(key)) {
          costs.remove(key);
          costs.put(key, new_cost);
          parents.remove(key);
          parents.put(key, node.getValue());
        }
      });
      processed.add(node.getValue());
      node.setValue(find_lowest_cost_node(costs, processed));
    }
    System.out.println(costs);
    System.out.println(parents);
    printResult(costs, parents);
  }

  private static String find_lowest_cost_node(HashMap<String, Float> costs, List<String> processed) {
    final Optional<String> lowest_cost_node = Optional.getInstance();
    final Optional<Float> lowest_cost = Optional.getInstance(Float.POSITIVE_INFINITY);

    costs.forEach((key, value) -> {
      if (!processed.contains(key) && value < lowest_cost.getFloat()) {
        lowest_cost_node.setValue(key);
        lowest_cost.setValue(value);
      }
    });
    return lowest_cost_node.getValue();
  }

  /**
   * 打印Dijkstra算法的结果
   */
  private static void printResult(HashMap<String, Float> costs, HashMap<String, String> parents) {
    System.out.println("--------------------------------------");
    System.out.print("The path is : start-->");
    String node = findParent(parents, "start");
    while (Objects.nonNull(node) && !Objects.equals(node, "fin")) {
      System.out.print(node + "-->");
      node = findParent(parents, node);
    }
    System.out.println("fin");
    System.out.println("The total cost is : " + costs.get("fin"));
  }

  private static String findParent(HashMap<String, String> parents, String node) {
    Optional<String> parent = Optional.getInstance(null);
    parents.forEach((key, value) -> {
      if (Objects.equals(value, node)) {
        parent.setValue(key);
      }
    });
    return parent.getValue();
  }
}
